/**
题目:
    对链表进行插入排序。
    插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
    每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
    插入排序算法：
    插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
    每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
    重复直到所有输入数据插入完为止。
思路:
    for循环 处理编辑
效果:
    执行用时：24 ms, 在所有 Go 提交中击败了38.53%的用户
    内存消耗：3.3 MB, 在所有 Go 提交中击败了26.62%的用
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 
4 2 1 3
2 4 1 3
1 2 3 4
 */
func insertionSortList(head *ListNode) *ListNode {
    if head == nil ||  head.Next == nil{
        return head
    }
    dummy := &ListNode{Next:head}
    cur := head.Next
    head.Next = nil
    for cur != nil{
        tmp := dummy
        next := cur.Next
        for tmp.Next != nil &&  tmp.Next.Val <= cur.Val{
            tmp = tmp.Next
        }
        cur.Next = tmp.Next
        tmp.Next = cur
        cur = next
    }
    return dummy.Next
}
